package com.tgy.排序;

import java.util.Arrays;

/***
 * @ClassName: SelectSort
 * @Description: 选择排序
 * @Auther: tanggy3
 * @Date: 11:13 2022/8/12
 * @version : V1.0
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        System.out.println(Arrays.toString(selectSortFinal(arr)));
        int[] intArr = Utils.getIntArr();
        int[] clone = intArr.clone();
        int[] clone1 = intArr.clone();
        int[] clone2 = intArr.clone();
        selectSortOnce(intArr);//2701ms
        selectSortPlus1(clone1);//2659ms
        selectSortPlus2(clone2);//2659ms
        selectSortFinal(clone);//2243ms

        //System.out.println(Arrays.toString(selectSortFinal(getIntArr())));//2583ms
    }


    /**
     * 细节版本
     *
     * @param arr
     * @return
     */
    public static int[] selectSortDetails(int[] arr) {
        int index = 0;
        int min = arr[0];
        for (int i = 0 + 1; i < arr.length; i++) {
            if (min > arr[i]) {//说明假定的数并不是是最小，需要从新设置;
                index = i;
                min = arr[i];
            }
        }
        //将最小值放在arr[0],交换位置
        arr[index] = arr[0];
        arr[0] = min;
        System.out.println("第一轮结束" + Arrays.toString(arr));

        index = 1;
        min = arr[1];
        for (int i = 0 + 1 + 1; i < arr.length; i++) {
            if (min > arr[i]) {//说明假定的数并不是是最小，需要从新设置;
                index = i;
                min = arr[i];
            }
        }
        //将最小值放在arr[0],交换位置
        arr[index] = arr[1];
        arr[1] = min;
        System.out.println("第二轮结束" + Arrays.toString(arr));

        index = 2;
        min = arr[2];
        for (int i = 0 + 1 + 1 + 1; i < arr.length; i++) {
            if (min > arr[i]) {//说明假定的数并不是是最小，需要从新设置;
                index = i;
                min = arr[i];
            }
        }
        //将最小值放在arr[0],交换位置
        arr[index] = arr[2];
        arr[2] = min;
        System.out.println("第三轮结束" + Arrays.toString(arr));
        return arr;
    }


    /**
     * 最终版本
     * 最快
     * @param arr
     * @return
     */
    public static int[] selectSortFinal(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            boolean flag = false;
            //记录下首位的下标
            int index = i;
            for (int j = i + 1; j < length; j++) {
                //如果有比当前下标元素小的元素就把下标替换为小的那个的下标，这样下标对应的元素遍历一遍就是最小的。
                if (arr[index] < arr[j]) {
                    index = j;
                    flag = true;
                }
            }
            if (flag) {
                //遍历完成后找到了最小数的下标，然后替换的相应的位置（第i个元素，第i个大周期）
                int tem = arr[index];
                arr[index] = arr[i];
                arr[i] = tem;
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }


    public static int[] selectSortOnce(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            //记录下首位的下标
            int index = i;
            for (int j = i + 1; j < length; j++) {
                //如果有比当前下标元素小的元素就把下标替换为小的那个的下标，这样下标对应的元素遍历一遍就是最小的。
                if (arr[index] < arr[j]) {
                    index = j;
                }
            }
            //遍历完成后找到了最小数的下标，然后替换的相应的位置（第i个元素，第i个大周期）
            int tem = arr[index];
            arr[index] = arr[i];
            arr[i] = tem;
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }


    public static int[] selectSortPlus1(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            //记录下首位的下标
            int index = i;
            int min = arr[i];
            for (int j = i + 1; j < length; j++) {
                //如果有比当前下标元素小的元素就把下标替换为小的那个的下标，这样下标对应的元素遍历一遍就是最小的。
                if (arr[index] < arr[j]) {
                    index = j;
                    min = arr[j];
                }
            }

            if (index != i) {
                //遍历完成后找到了最小数的下标，然后替换的相应的位置（第i个元素，第i个大周期）
                arr[index] = arr[i];
                arr[i] = min;
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }


    /**
     *
     * @param arr
     * @return
     */
    public static int[] selectSortPlus2(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;
        int tem = 0;
        for (int i = 0; i < length - 1; i++) {
            //记录下首位的下标
            int index = i;
            for (int j = i + 1; j < length; j++) {
                //如果有比当前下标元素小的元素就把下标替换为小的那个的下标，这样下标对应的元素遍历一遍就是最小的。
                if (arr[index] < arr[j]) {
                    index = j;
                }
            }

            if (index != i) {
                //遍历完成后找到了最小数的下标，然后替换的相应的位置（第i个元素，第i个大周期）
                tem = arr[index];
                arr[index] = arr[i];
                arr[i] = tem;
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }
}
